class Solution {
public:
    string dp[12][5005];
    string largestNumber(vector<int>& cost, int target) {
        cost.insert(cost.begin(), 0);
        for (int i = 1; i <= target; i++) dp[cost.size()][i] = "0";
        for (int i = cost.size() - 1; i >= 1; i--)
        {
            for (int j = 1; j <= target; j++)
            {
                dp[i][j] = dp[i + 1][j];
                if (j >= cost[i])
                {
                    string a = dp[i + 1][j];
                    if (dp[i][j - cost[i]] == "0") continue;
                    string b = dp[i][j - cost[i]];
                    b += i + '0';
                    if (b.size() > a.size()) dp[i][j] = b;
                    else if (a.size() == b.size()) dp[i][j] = max(a, b);
                }
            }
        }
        return dp[1][target];
    }
};